home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / listings / v_11_05 / 1105035a < prev    next >
Text File  |  1993-03-02  |  15KB  |  767 lines
  1. // ==================================================================
  2. // btree.h
  3. //    Template-based balanced binary tree class.
  4. //    Copyright (C) 1992 by Nicholas Wilt.  All rights reserved.
  5. // ==================================================================
  6.  
  7. #ifndef __BTREE__
  8.  
  9. #define __BTREE__
  10.  
  11. // BinaryNode is the class template that does all the work.
  12. // All the binary tree primitives are implemented in here.
  13. template<class T>
  14. class BinaryNode {
  15. protected:
  16.     // For node colors
  17.     enum RedBlack { Black, Red };
  18. public:
  19.     T x;                // Node contents
  20.     enum RedBlack clr;            // Color of node (red or black)
  21.     BinaryNode<T> *l, *r, *p;        // Left, right and parent pointers
  22.  
  23. protected:
  24.     // Tree manipulations used during insertion and deletion
  25.     virtual BinaryNode<T> *LeftRotate(BinaryNode<T> *root);
  26.     virtual BinaryNode<T> *RightRotate(BinaryNode<T> *root);
  27.     virtual BinaryNode<T> *DeleteFixup(BinaryNode<T> *x, BinaryNode<T> *p);
  28.  
  29. public:
  30.     // Constructors.  Node always starts out red.
  31.     BinaryNode();
  32.     BinaryNode(const T& X, BinaryNode<T> *P = 0, 
  33.     BinaryNode<T> *L = 0, BinaryNode<T> *R = 0);
  34.     virtual ~BinaryNode() { }
  35.     static void PostOrderDeletion(BinaryNode<T> *r);
  36.     virtual BinaryNode<T> *Dup(BinaryNode<T> *P) const;
  37.  
  38.     // Operations defined on binary trees.  All run in O(lgN) time.
  39.     virtual BinaryNode<T> *Min();
  40.     virtual BinaryNode<T> *Max();
  41.     virtual BinaryNode<T> *Pred();
  42.     virtual BinaryNode<T> *Succ();
  43.     virtual BinaryNode<T> *Query(const T& q);
  44.     virtual BinaryNode<T> *InsertNode(BinaryNode<T> *root);
  45.     virtual BinaryNode<T> *Insert(const T& AddMe);
  46.     virtual BinaryNode<T> *DeleteNode(BinaryNode<T> *z);
  47.     virtual BinaryNode<T> *DeleteItem(const T& q);
  48.     virtual BinaryNode<T> *DeletePassbk(T q, T *passbk);
  49.  
  50.     // Returns 0 if the red-black invariant holds.
  51.     virtual int CheckInvariant(int i, int num);
  52.  
  53.     // Returns number of black nodes from root to leftmost node.
  54.     int BlackToMin();
  55. };
  56.  
  57.  
  58. template<class T>
  59. class BinaryTreeIter {
  60. public:
  61.     // Create iterator for tree, initially pointing at root.
  62.     BinaryTreeIter(BinaryTree<T>& tree);
  63.  
  64.     // Create iterator for tree, initially pointing at the node
  65.     // queried by q.
  66.     BinaryTreeIter(BinaryTree<T>& tree, const T& q);
  67.  
  68.     // Reset iterator to point to root of given tree.
  69.     void Reset(BinaryTree<T>& tree);
  70.  
  71.     // Returns pointer to the contents of the current node, or
  72.     // 0 if the current node is 0.
  73.     T *Contents() const;
  74.  
  75.     // Sets iterator to point to minimum node in the subtree.
  76.     void Min();
  77.  
  78.     // Sets iterator to point to maximum node in the subtree.
  79.     void Max();
  80.  
  81.     // Sets iterator to point to the current node's predecessor.
  82.     void Pred();
  83.  
  84.     // Sets iterator to point to the current node's successor.
  85.     void Succ();
  86.  
  87.     // Queries subtree for the given key.
  88.     int Query(const T&);
  89.  
  90. protected:
  91.     BinaryTree<T> *tree;    // Pointer to the tree being scanned
  92.  
  93.     BinaryNode<T> *subtree;    // Subtree currently being considered
  94. };
  95.  
  96. // BinaryTree class template.
  97. template<class T> 
  98. class BinaryTree {
  99.  
  100. protected:
  101.     BinaryNode<T> *root;
  102.  
  103. public:
  104.     // Default constructor.
  105.     BinaryTree();
  106.  
  107.     // Copy constructor.
  108.     BinaryTree(const BinaryTree<T>& x);
  109.  
  110.     // Assignment operator.
  111.     BinaryTree<T>& operator= (const BinaryTree<T>& x);
  112.  
  113.     // Destructor.
  114.     ~BinaryTree();
  115.  
  116.     virtual T *Min() const;
  117.     virtual T *Max() const;
  118.     virtual T *Pred(const T& q) const;
  119.     virtual T *Succ(const T& q) const;
  120.     virtual T *Query(const T& q) const;
  121.     virtual void Insert(const T& addme);
  122.     virtual void DeleteItem(const T& q);
  123.     virtual void DeletePassbk(const T& q, T *passbk);
  124.     virtual int IsEmpty() const;
  125.     virtual int CheckInvariant();
  126.  
  127. // The following are accessible only to classes that inherit
  128. // from BinaryTree, since they deal directly with BinaryNodes.
  129. protected:
  130.     virtual BinaryNode<T> *InsertPassbk(const T& addme);
  131.     virtual BinaryNode<T> *QueryNode(const T& q) const;
  132.     virtual void DeleteNode(BinaryNode<T> *delme);
  133.  
  134.     friend BinaryTreeIter<T>;
  135. };
  136.  
  137. template<class T>
  138. BinaryTreeIter<T>::BinaryTreeIter(BinaryTree<T>& Tree)
  139. {
  140.     tree = &Tree;
  141.     subtree = tree->root;
  142. }
  143.  
  144. template<class T>
  145. BinaryTreeIter<T>::BinaryTreeIter(BinaryTree<T>& Tree, const T& q)
  146. {
  147.     tree = &Tree;
  148.     subtree = tree->root;
  149.     if (subtree)
  150.     subtree = subtree->Query(q);
  151. }
  152.  
  153. template<class T>
  154. void
  155. BinaryTreeIter<T>::Reset(BinaryTree<T>& Tree)
  156. {
  157.     tree = &Tree;
  158.     subtree = tree->root;
  159. }
  160.  
  161. template<class T>
  162. T *
  163. BinaryTreeIter<T>::Contents() const
  164. {
  165.     return (subtree) ? &subtree->x : 0;
  166. }
  167.  
  168. template<class T>
  169. void
  170. BinaryTreeIter<T>::Min()
  171. {
  172.     if (subtree)
  173.     subtree = subtree->Min();
  174. }
  175.  
  176. template<class T>
  177. void
  178. BinaryTreeIter<T>::Max()
  179. {
  180.     if (subtree)
  181.     subtree = subtree->Max();
  182. }
  183.  
  184. template<class T>
  185. void
  186. BinaryTreeIter<T>::Pred()
  187. {
  188.     if (subtree)
  189.     subtree = subtree->Pred();
  190. }
  191.  
  192. template<class T>
  193. void
  194. BinaryTreeIter<T>::Succ()
  195. {
  196.     if (subtree)
  197.     subtree = subtree->Succ();
  198. }
  199.  
  200. template<class T>
  201. int
  202. BinaryTreeIter<T>::Query(const T& x)
  203. {
  204.     subtree = (subtree) ? subtree->Query(x) : 0;
  205.     return subtree != 0;
  206. }
  207.  
  208.     // Private enum to implement the red-black tree.
  209. //    enum RedBlack { Black, Red };
  210.  
  211. template<class T>
  212. BinaryTree<T>::BinaryTree()
  213. {
  214.     root = 0;
  215. }
  216.  
  217. template<class T>
  218. BinaryTree<T>::BinaryTree(const BinaryTree<T>& x)
  219. {
  220.     root = x.root->Dup(0);
  221. }
  222.  
  223. template<class T>
  224. BinaryTree<T>&
  225. BinaryTree<T>::operator=(const BinaryTree<T>& x)
  226. {
  227.     BinaryNode<T>::PostOrderDeletion(root);
  228.     root = x.root->Dup(0);
  229.     return *this;
  230. }
  231.  
  232. template<class T>
  233. BinaryTree<T>::~BinaryTree()
  234. {
  235.     BinaryNode<T>::PostOrderDeletion(root);
  236. }
  237.  
  238. template<class T>
  239. T *
  240. BinaryTree<T>::Min() const
  241. {
  242.     return (root) ? &root->Min()->x : 0;
  243. }
  244.  
  245. template<class T>
  246. T *
  247. BinaryTree<T>::Max() const
  248. {
  249.     return (root) ? &root->Max()->x : 0;
  250. }
  251.  
  252. template<class T>
  253. T *
  254. BinaryTree<T>::Pred(const T& q) const
  255. {
  256.     BinaryNode<T> *p = (root) ? root->Query(q) : 0;
  257.     if (p) {
  258.         BinaryNode<T> *r = p->Pred();
  259.         return (r) ? &r->x : 0;
  260.     }
  261.     else return 0;
  262. }
  263.  
  264. template<class T>
  265. T *
  266. BinaryTree<T>::Succ(const T& q) const
  267. {
  268.     BinaryNode<T> *p = (root) ? root->Query(q) : 0;
  269.     if (p) {
  270.         BinaryNode<T> *r = p->Succ();
  271.         return (r) ? &r->x : 0;
  272.     }
  273.     else return 0;
  274. }
  275.  
  276. template<class T>
  277. T *
  278. BinaryTree<T>::Query(const T& q) const
  279. {
  280.     BinaryNode<T> *p = (root) ? root->Query(q) : 0;
  281.     return (p) ? &p->x : 0;
  282. }
  283.  
  284. template<class T>
  285. void
  286. BinaryTree<T>::Insert(const T& addme)
  287. {
  288.     if (root)
  289.     root = root->Insert(addme);
  290.     else
  291.     root = new BinaryNode<T>(addme);
  292. }
  293.  
  294. template<class T>
  295. BinaryNode<T> *
  296. BinaryTree<T>::InsertPassbk(const T& addme)
  297. {
  298.     if (root)
  299.         root = root->Insert(addme);
  300.     else
  301.         root = new BinaryNode<T>(addme);
  302.     return root->Query(addme);
  303. }
  304.  
  305. template<class T>
  306. void
  307. BinaryTree<T>::DeleteItem(const T& q)
  308. {
  309.     if (root)
  310.     root = root->DeleteItem(q);
  311. }
  312.  
  313. template<class T>
  314. void
  315. BinaryTree<T>::DeletePassbk(const T& q, T *passbk)
  316. {
  317.     if (root)
  318.         root = root->DeletePassbk(q, passbk);
  319. }
  320.  
  321. template<class T>
  322. int
  323. BinaryTree<T>::IsEmpty() const
  324. {
  325.     return root == 0;
  326. }
  327.  
  328. template<class T>
  329. int
  330. BinaryTree<T>::CheckInvariant()
  331. {
  332.     return (root) ? root->CheckInvariant(0, root->BlackToMin()) : 0;
  333. }
  334.  
  335. template<class T>
  336. BinaryNode<T> *
  337. BinaryTree<T>::QueryNode(const T& q) const
  338. {
  339.     return (root) ? root->Query(q) : 0;
  340. }
  341.  
  342. template<class T>
  343. void
  344. BinaryTree<T>::DeleteNode(BinaryNode<T> *delme)
  345. {
  346.     if (root)
  347.     root = root->DeleteNode(delme);
  348. }
  349.  
  350. template<class T>
  351. BinaryNode<T>::BinaryNode()
  352. {
  353.     clr = Red;
  354.     l = r = p = 0;
  355. }
  356.  
  357. template<class T>
  358. BinaryNode<T>::BinaryNode(const T& X, BinaryNode<T> *P = 0,
  359.     BinaryNode<T> *L = 0, BinaryNode<T> *R = 0): x(X)
  360. {
  361.     clr = Red;
  362.     p = P;
  363.     l = L;
  364.     r = R;
  365. }
  366.  
  367. template<class T>
  368. void
  369. BinaryNo